// // class Solution
// // {
// //     int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1};
// //     int dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};
// //     int m, n;

// // public:
// //     vector<vector<char>> updateBoard(vector<vector<char>> &board, vector<int> &
// //                                                                       click)
// //     {
// //         m = board.size(), n = board[0].size();
// //         int x = click[0], y = click[1];
// //         if (board[x][y] == 'M') // 直接点到地雷
// //         {
// //             board[x][y] = 'X';
// //             return board;
// //         }
// //         dfs(board, x, y);
// //         return board;
// //     }
// //     void dfs(vector<vector<char>> &board, int i, int j)
// //     {
// //         // 统计⼀下周围的地雷个数
// //         int count = 0;
// //         for (int k = 0; k < 8; k++)
// //         {
// //             int x = i + dx[k], y = j + dy[k];
// //             if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M')
// //             {
// //                 count++;
// //             }
// //         }
// //         if (count) // 周围有地雷
// //         {
// //             board[i][j] = count + '0';
// //             return;
// //         }
// //         else // 周围没有地雷
// //         {
// //             board[i][j] = 'B';
// //             for (int k = 0; k < 8; k++)
// //             {
// //                 int x = i + dx[k], y = j + dy[k];
// //                 if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E')
// //                 {
// //                     dfs(board, x, y);
// //                 }
// //             }
// //         }
// //     }
// // };

// // #include <iostream>
// // #include <algorithm>
// // using namespace std;
// // long long n, m, a, b;

// // int main()
// // {
// //     cin >> n >> m >> a >> b;
// //     long long ret = 0;
// //     for (int i = 0; 2 * i <= n && i <= m; ++i)
// //     {
// //         long long tmpn = n, tmpm = m;
// //         long long cnt = i * a;
// //         tmpn -= 2 * i, tmpm -= i;
// //         cnt += min(tmpn, tmpm / 2) * b;

// //         ret = max(ret, cnt);
// //     }

// //     std::cout << ret << endl;
// //     return 0;
// // }

// // I like beijing.
// // beijing. like I

// string s ;

// void Reverse(int left, int right)
// {
//     while (left < right)
//     {
//         char tmp = s[left];
//         s[left] = s[right];
//         s[right] = tmp;
//         left++, right--;
//     }
// }
// int main()
// {
//     getline(cin, s);
//     int n = s.size();
//     Reverse(0, n - 1);
//     int left = 0;
//     for (int i = 0; i < n; ++i)
//     {
//         if (i < n - 1 && s[i + 1] == ' ')
//         {
//             Reverse(left, i);
//             left = i + 2;
//         }
//     }
//     Reverse(left, n - 1);
//     cout << s << endl;
//     return 0;
// }

// 5
// 5 4 3 2 1
// #include <iostream>
// #include <algorithm>
// #include <string>
// #include <vector>
// using namespace std;
// int main() {
//     int n;
//     cin >> n;
//     int prices[n];
//     for (int i = 0; i < n; i++) {
//         cin >> prices[i];
//     }
//     int dp[n][2];//0卖出
//     dp[0][1] = -prices[0];
//     for (int i = 1; i < n; i++) {
//         dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
//         dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
//     }
//     cout << dp[n - 1][0] << endl;
//     return 0;
// }